#include <stdio.h>
#include <string.h>

void GetNext(const char *T,int *next)
{
    int i = 1;
    next[1] = 0;
    int j = 0;

    while(i < (strlen(T) - 1)){
        if (j == 0 || T[i] == T[j]){
            i++;
            j++;
            next[i] = j;
        }
        else j = next[j];
    }
}

int Index(const char *S,const char *T,int pos,int *next)
{
    int i = pos;
    int j = 1;

    while(i <= (strlen(S) - 1) && j <= (strlen(T)- 1)){
        if (j == 0 || S[i] == T[j]){
                i++;
                j++;
        }
        else j = next[j];
    }
    if (j > strlen(T) - 1)
        return (i - (strlen(T) -1));
    else return 0;
}

int main()
{
    char S[] = " 123ab12ab1ad";
    char T[] = " ab1a";
    int next[10];
    int pos;

    printf("S:%s\n",S);
    printf("T:%s\n",T);
    memset(next,0,sizeof(next));

    printf("sizeof(next) = %d\n",sizeof(next));

    GetNext(T,next);
    for(pos = 0;pos < sizeof(next)/sizeof(int);pos++){
        printf("next[%d] = %d\n",pos,next[pos]);
    }

    pos = Index(S,T,1,next);

    printf("pos = %d\n",pos);

    return 0;
}

